/**
 * 300. 最长上升子序列
 * <p>
 * 给定一个无序的整数数组，找到其中最长上升子序列的长度。
 * <p>
 * 示例:
 * <p>
 * 输入: [10,9,2,5,3,7,101,18]
 * 输出: 4
 * 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
 * <p>
 * 说明:
 * <p>
 * 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
 * 你算法的时间复杂度应该为 O(n2) 。
 * <p>
 * 动态规划：
 * f(n)，表示前n个字符的最常上升子序列
 * <p>
 * 如果 当前的数 大于要与之比较的序列的最后一个数，就说明存在新的上升子序列
 */

public class Solution_300 {
    public static void main(String[] args) {
        System.out.println(lengthOfLIS1(new int[]{0, 1, 0, 3, 2, 3}));
    }

    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        //用于保存前n个子串的最常上升子序列长度
        int cach[] = new int[n];

        //初始化
        for (int i = 0; i < n; i++) {
            cach[i] = 1;
        }

        /**
         * i:外循环，用于从1~n找出最长子序列的长度
         * j:内循环，用于循环比较前j个序列与第i个数是否能组成新的上升子序列
         * max:用于记录当前最长的子序列的长度
         */
        int i, j, max = 0;

        for (i = 0; i < n; i++) {
            for (j = 0; j < i; j++) {
                if (nums[j] < nums[i] && cach[i] < cach[j] + 1) {
                    cach[i] = cach[j] + 1;
                }
            }

            max = Math.max(max, cach[i]);
        }

        return max;
    }

    static public int lengthOfLIS1(int[] nums) {
        int n = nums.length;
        //用于保存前n个子串的最常上升子序列长度
        int dp[] = new int[n];

        //初始化
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        // 记录当前最大的子序列长度
        int max = dp[0];
        int maxPre;
        for (int i = 1; i < nums.length; i++) {
            // 遍历前面的，看是否可以进行拼接
            for (int j = i - 1; j >= 0; j--) {
                // 如果可以拼接，并且拼接后的新长度比原来长，则重新拼接
                if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                }
            }
            max = Math.max(dp[i], max);
        }
        return max;
    }
}
